package 代码随想录.单调栈.接雨水;

import java.util.Deque;
import java.util.LinkedList;

public class LeetCode42 {
    //列方向
    //双指针法，找每个柱子的左边最大高度和右边最大高度
    //当前柱子能接到的雨水=min(左边柱子的最大高度，右边柱子的最大高度)-当前柱子高度
    public int trap(int[] height) {
        int sum = 0;
        int len = height.length;
        for (int i = 0; i < len; i++) {
            //第一个柱子和最后一个柱子不接雨水
            if (i == 0 || i == len - 1) {
                continue;
            }
            int right = height[i];//记录
            int left = height[i];
            //找右边柱子的最大高度
            for (int j = i + 1; j < len; j++) {
                right = Math.max(right, height[j]);
            }
            //找左边柱子的最大高度
            for (int j = i; j >= 0; j--) {
                left = Math.max(left, height[j]);
            }
            //当前柱子能接到的雨水=min(左边柱子的最大高度，右边柱子的最大高度)-当前柱子高度
            //即res=min(left,right)-current
            sum += Math.min(left, right) - height[i];
        }
        return sum;
    }

    //行方向，这个画图比较好理解
    //单调递减栈，因为雨水只会在低洼处形成，所以是单调递减栈
    //如果碰到比栈顶元素大的值，说明可以形成低洼。
    public int trap1(int[] height) {
        int sum = 0;
        Deque<Integer> stack = new LinkedList<>();
        int len = height.length;
        for (int i = 0; i < len; i++) {
            int current = height[i];
            while (!stack.isEmpty() && current > height[stack.peek()]) {
                Integer pop = stack.pop();
                if (stack.isEmpty()) {
                    break;
                }
                int left = stack.peek();  //低洼的左边
                //计算宽度
                int curWidth = i - left - 1;
                //计算高度:低洼左边和右边的最小值减去当前柱子本身的高度
                int curHeight = Math.min(height[left], current) - height[pop];
                sum += curWidth * curHeight;
            }
            stack.push(i);
        }
        return sum;
    }

    public static void main(String[] args) {
        LeetCode42 code42 = new LeetCode42();
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int sum = code42.trap(height);
        int sum1 = code42.trap1(height);
        System.out.println(sum);
        System.out.println(sum1);
    }
}
